class Solution {
    public int[] sortArray(int[] nums) {
        qSort(nums,0,nums.length-1);
        return nums;
    }
    public void qSort(int[] nums,int l,int r){
        if(l>=r) return;
        int key=nums[new Random().nextInt(r-l+1)+l];
        int left=l-1,right=r+1,i=l;
        while(i<right){
            if(nums[i]<key)
                swap(nums,i++,++left);
            else if(nums[i]==key)
                i++;
            else{
                swap(nums,i,--right);
            }
        }
        qSort(nums,l,left);
        qSort(nums,right,r);
    }
    public void swap(int[] nums,int i,int j){
        int t=nums[i];
        nums[i]=nums[j];
        nums[j]=t;
    }
}